package com.my.ds.impl.tree;

/**
 * <p>二叉查找树实现（链式存储法）</p>
 * <p>二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值</p>
 * <p><a href="https://www.cs.usfca.edu/~galles/visualization/BST.html">Binary Search Tree动画演示</a></p>
 *
 * @author: marshal
 * @date: 2023-02-17 15:17
 */
public class BinarySearchTree {

    /**
     * 根节点
     */
    private Node tree;

    /**
     * 节点数据结构
     */
    public static class Node {
        // 存储的数据
        private int data;
        // 左指针
        private Node left;
        // 右指针
        private Node right;

        public Node(int data) {
            this.data = data;
        }
    }

    /**
     * 根据元素查找
     * <p>
     * 首先，我们看如何在二叉查找树中查找一个节点。我们先取根节点， 如果它等于我们要查找的数据，那就返回。 如果要查找的数据比根节点的值小，那就在左子树中递归查找； 如果要查找的数据比根节点的值大，那就在右子树中递归查找。
     * </p>
     *
     * @param data 元素
     * @return 目标节点
     */
    public Node find(int data) {
        Node p = tree;
        while (p != null) {
            if (data > p.data) {
                p = p.right;
            } else if (data < p.data) {
                p = p.right;
            } else {
                return p;
            }
        }
        return null;
    }

    /**
     * 插入数据
     *
     * <p>新插入的数据一般都是在叶子节点上，所以我们只需要从根节点开始，依次比较要插入的数据和节点的大小关系。</p>
     * <p>如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。</p>
     * <p>同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。</p>
     *
     * @param data 数据
     */
    public void insert(int data) {
        // 树为空的时候
        if (tree == null) {
            tree = new Node(data);
            return;
        }
        Node p = tree;
        while (p != null) {
            if (data >= p.data) { // 插入右边，当插入的值等于节点值的时候，也是插入右边
                if (p.right == null) {
                    p.right = new Node(data);
                }
                // 移动指针
                p = p.right;
            } else { // 插入左边
                if (p.left == null) {
                    p.left = new Node(data);
                }
                // 移动指针
                p = p.left;
            }
        }
    }

    /**
     * 删除
     * <p>二叉查找树的删除比较复杂，分为以下几种情况：</p>
     * <p>1. 如果要删除的节点没有子节点，则直接将该节点的父节点指向该节点的指针设为null即可。</p>
     * <p>2. 如果要删除的节点有一个子节点（左节点或者右节点），则将该节点的父节点指向该节点的指针指向该节点的子节点即可。</p>
     * <p>
     * 3. 如果要删除的节点有两个子节点，则有两种删除方式，取其中之一即可
     * <p>3.1 找到该节点右子树中的最小节点，替换到该节点</p>
     * <p>3.2 找到该节点左子树中的最大节点，替换到该节点</p>
     * </p>
     *
     * @param data 要删除的数据
     */
    public void delete(int data) {
        Node p = tree;
        if (p == null) {
            throw new RuntimeException("当前二叉树是空的");
        }
        // 1. 找到要删除的节点

    }

    private Node findPreNode(Node node) {
        return null;
    }

    private Node findNextNode(Node node) {
        return null;
    }

    /**
     * 查找最大节点
     *
     * @return 最大节点
     */
    private Node findMaxNode() {
        Node p = tree;
        if (p == null) {
            return null;
        }
        // 最大值一定是在最右侧
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }

    /**
     * 查找最小节点
     *
     * @return 最小节点
     */
    private Node findMinNode() {
        Node p = tree;
        if (p == null) {
            return null;
        }
        // 最大值一定是在最左侧
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }
}
